﻿// 301 最短路.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <memory.h>

using namespace std;
/*
http://oj.daimayuan.top/course/14/problem/655

给你一张 n个顶点 m 条边的有向简单图，顶点编号从 1到 n
，每条边都有一个边权，边权为非负整数。

现在有 k组询问，每组询问读入两个整数 x,y
，请求出从 x号点到 y号点的最短路的长度。如果不存在从 x号点到 y号点的路径，请输出 -1。

输入格式
第一行三个整数 n,m,k，表示图的顶点数、边数和询问次数。

接下来 m行，每行三个整数 x,y,z，表示 x号点到 y号点有一条边权为 z的有向边。

接下来 k行，每行两个整数 x,y，表示一组询问。

输出格式
输出共 k行，每行一个数表示一组询问的答案。

样例输入
3 3 2
1 2 3
2 3 2
3 2 1
1 3
3 1
样例输出
5
-1
数据规模
对于所有数据，保证 2≤n≤5000,0≤m≤10000,1≤k≤5,1≤x,y≤n,1≤z≤10000。
*/
const int N = 5010, M = 10010;
int h[N], e[M], ne[M],w[M], idx;
int n, m, k;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra(int x, int y) {
	memset(dist, 0x3f, sizeof dist);
	dist[x] = 0;
	memset(st, 0, sizeof st);
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > heap;
	heap.push({ 0,x });

	while (!heap.empty()) {
		auto t = heap.top();
		heap.pop();

		int ver = t.second, distance = t.first;
		if (st[ver]) continue;
		st[ver] = true;

		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dist[j] > distance + w[i]) {
				dist[j] = distance + w[i];
				heap.push({ dist[j],j });
			}
		}
	}

	if (dist[y] == 0x3f3f3f3f) return -1;
	return dist[y];
}


int main()
{
	scanf("%d%d%d",&n,&m,&k);
	memset(h,-1,sizeof h);
	for (int i = 0; i < m; i++) {
		int a, b, c; scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}

	for (int i = 0; i < k; i++) {
		int a, b; scanf("%d%d",&a,&b);
		cout << dijkstra(a, b) << endl;
	}

	return 0;
}
 